Pada awalnya, gabungan ini digagas oleh jurubicara PKS Muhammad Kholid sesuai dengan hasil perhimpunan kepimpinan nasional atau Rapimnas PKS pada 2022.[5][6] Saat itu, PKS berikihtiar untuk membentuk gabungan baharu dengan prinsip perubahan, yakni perubahan agar Indonesia menjadi negara yang lebih adil, sejahtera, demokratik, bersatu dan berdaulat, serta memiliki peran strategik dalam perihal politik global.[7][8]

Pada 3 Oktober 2022, Partai NasDem pimpinan Surya Paloh secara rasmi mengiktiraf Anies Baswedan sebagai calon presiden dalam menghadapi pilihan raya presiden Indonesia 2024.[9]

Pada Disember, parti-parti lain mula mnyeatakan hasrat untuk menubuhkan gabungan pada Januari 2023.[10] Pada 26 Januari 2023, Ketua Umum Partai Demokrat, Agus Harimurti Yudhoyono mengeluarkan kenyataan tertulis yang menyatakan dukungan partinya kepada Anies Baswedan sebagai calon presiden.[11] Pada 30 Januari, setelah perbincangan dengan Ketua Umum dan Ketua Majelis Syura Partai Keadilan Sejahtera (PKB), timbalan ketua Majelis Syura PKB Sohibul Iman, menyatakan dukungan rasmi terhadap Anies Baswedan sebagai calon presiden.[12]

Pernyataan ini menjadikan Anies Baswedan sebagai bakal calon presiden pertama yang memenuhi syarat ambang batas presiden dan telah dideklarasikan.[13] Ketiga-tiga parti pendukung sepakat bahwa Anies yang akan menentukan siapa pasangan calon wakil presidennya.[14] Teuku Riefky Harsya, ketua setiausaha Partai Demokrat, menyatakan bahwa ketua ketiga-tiga parti akan menandatangani kontrak kerjasama secepatnya.[15]

Pada 24 Mac 2023, Tim Kecil yang sejak awal menyusun arah pembentukkan gabungan mengumumkan bahwa ketiga-tiga ketua parti anggota telah menandatangani nota kesepakatan pendirian Koalisi Perubahan untuk Persatuan. Dalam acara penunjukan plakat nota kesepakatan tersebut, Tim Kecil Perubahan dihadiri oleh Sudirman Said (jurubicara Anies Baswedan), Teuku Riefky Harsya (setiausaha agung Partai Demokrat), Willy Aditya (ketua Partai NasDem), Sugeng Suparwoto (Ketua Tim Pemenangan Partai NasDem), Mohamad Sohibul Iman (naib ketua Majelis Syura PKS), dan Al-Muzzammil Yusuf (ketua PKS).[16]

Pada 1 September 2023, Partai Demokrat keluar daripada gabungan lalu menarik sokongan kepada Anies Baswedan dalam pilihan raya 2024.[17] Sementara itu, Partai Kebangkitan Bangsa (PKB) pula memasuki gabungan. Pada 2 September, pengisytiharan pencalonan pasangan Anies Baswedan dan Muhaimin Iskandar sebagai calon presiden dan timbalan presiden dibuat di Hotel Majapahit, Surabaya.[18]